package difficult.array;

import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeMap;

/**
 * <a href="https://leetcode.cn/problems/number-of-flowers-in-full-bloom/description">2251. 花期内花的数目</a>
 * 给你一个下标从 0 开始的二维整数数组 flowers ，其中 flowers[i] = [starti, endi] 表示第 i 朵花的 花期 从 starti 到 endi （都 包含）。同时给你一个下标从 0 开始大小为 n 的整数数组 people ，people[i] 是第 i 个人来看花的时间。
 * 请你返回一个大小为 n 的整数数组 answer ，其中 answer[i]是第 i 个人到达时在花期内花的 数目 。
 * 示例 1：
 *   输入：flowers = [[1,6],[3,7],[9,12],[4,13]], people = [2,3,7,11]
 *   输出：[1,2,2,2]
 *   解释：上图展示了每朵花的花期时间，和每个人的到达时间。
 *     对每个人，我们返回他们到达时在花期内花的数目。
 * 示例 2：
 *   输入：flowers = [[1,10],[3,3]], people = [3,3,2]
 *   输出：[2,2,1]
 *   解释：上图展示了每朵花的花期时间，和每个人的到达时间。
 *     对每个人，我们返回他们到达时在花期内花的数目。
 * 提示：
 *   1 <= flowers.length <= 5 * 10^4
 *   flowers[i].length == 2
 *   1 <= starti <= endi <= 10^9
 *   1 <= people.length <= 5 * 10^4
 *   1 <= people[i] <= 10^9
 * @author 刘学松
 * @date 2023-09-28 15:44
 */
public class 花期内花的数目 {
    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int[] flower : flowers) {
            map.merge(flower[0], 1, Integer::sum);
            map.merge(flower[1] + 1, -1, Integer::sum);
        }
        Integer[] mapping = new Integer[people.length];
        for (int i = 0; i < mapping.length; i++) {
            mapping[i] = i;
        }
        Arrays.sort(mapping, Comparator.comparingInt(x -> people[x]));

        int count = 0;
        int[] ans = new int[people.length];
        for (Integer integer : mapping) {
            while (!map.isEmpty() && map.firstKey() <= people[integer]) {
                count += map.pollFirstEntry().getValue();
            }
            ans[integer] = count;
        }
        return ans;
    }
}
